package leetcode.剑指offer.剑指II;

import leetcode.剑指offer.pojo.ListNode;
import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/8/18 20:36
 * @description：https://leetcode-cn.com/problems/c32eOV/
 */
public class 链表中环的入口节点 {
    @Test
    public void test() {
        Solution solution = new Solution();
    }

    public class Solution {
        public ListNode detectCycle(ListNode head) {
            if (head == null) return null;
            ListNode slow = head, fast = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) {
                    ListNode ptr = head;
                    while (ptr != slow) {
                        ptr = ptr.next;
                        slow = slow.next;
                    }
                    return slow;
                }
            }
            return null;
        }
    }
}
